<?php

/**
 * 链表的实现
 * Class LinkedList
 */
class LinkedList
{
    private $head;

    /**
     * 初始化链表 null->null
     * LinkedList constructor.
     */
    public function __construct()
    {
        $this->head = null;
        $this->size = 0;
    }

    public function recursionLinkedList(){
        $this->head = $this->recursion($this->head);
    }

    private function recursion($head){
        if($head->next == null){
            return $head;
        }

        $cur = $head;
        $next = $this->recursion($head->next);//这个想象成一个已经翻转的链表其返回值是头
        $head->next->next = $head;//需要得到递归整体链表的尾部，有一种low办法就是遍历，但在这里可以直接取 $head节点的 next 节点，因为其指向的地址没有变
        $head->next = null;//原来的头需要指向null

        return $next;//最后需要返回递归整体这个链表
    }


    /**
     * 判断链表是否为空
     * @return bool
     */
    public function isEmpty(): bool
    {
        return $this->size == 0;
    }

    /**
     * 向链表开头添加元素
     * @param $e
     */
    public function addFirst($e): void
    {
        if($this->head == null){
            $this->head = new Node($e,null);
        }else{
            $node = new Node($e,$this->head);
            $this->head = $node;
        }
    }

    /**
     * 判断链表中是否存在某个元素
     * @param $e
     * @return bool
     */
    public function contains($e): bool
    {
        for ($node = $this->head; $node != null; $node = $node->next) {
            if ($node->e == $e) {
                return true;
            }
        }
        return true;
    }

    public function getHead(){
        return $this->head;
    }

    public function setHead($head){
        $this->head = $head;
    }

    /**
     * 链表元素转化为字符串显示
     * @return string
     */
    public function toString(): string
    {
        $str = "";
        for ($node = $this->head; $node != null; $node = $node->next) {
            $str .= $node->e . "->";
        }
        return $str . "null";
    }
}

class Node
{
    public $e;//节点元素
    public $next; //下个节点信息

    /**
     * 构造函数 设置节点信息
     * Node constructor.
     * @param $e
     * @param $next
     */
    public function __construct($e, $next=null)
    {
        $this->e = $e;
        $this->next = $next;
    }
}

